#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "BinaryTree.h"



struct BinaryTreeNode
{
    //数据域
    ElementType data;
    //左孩子
    BTNode *left;
    //右孩子
    BTNode *right;
    //双亲节点指针
    BTNode *parent;
};

//创建节点
BTNode *CreateBTNode(ElementType element)
{
    BTNode *newNode = (BTNode*)malloc(sizeof(BTNode));
    if(newNode == NULL)
    {
        printf("create node malloc error!\n");
        return NULL;
    }

    newNode->data = element;
    newNode->left = newNode->right = newNode->parent = NULL;
    return newNode;
}

//往一个节点中插入一个元素
<<<<<<< HEAD
void InsertNodeTree(BTNode *node,ElementType element,int(*funcPtr)(ElementType,ElementType))
=======
void InsertNode(BTNode *node,ElementType element,int(*funcPtr)(ElementType,ElementType))
>>>>>>> 0979c5004e24bc00a548bec8efd3b8a77e34ab35
{
    if(node == NULL)
        return;
    
    //元素比节点小且左孩子为空
    if(funcPtr(node->data,element) > 0 && node->left == NULL)
    {
        node->left = CreateBTNode(element);
        if(node->left == NULL)
            return;
        //将创建节点的双亲指向自己
        node->left->parent = node;
        return;
    }

    //元素比节点大且右孩子为空
    if(funcPtr(node->data,element) < 0 && node->right == NULL)
    {
        node->right = CreateBTNode(element);
        if(node->right == NULL)
            return;
        //将创建节点的双亲指向自己
        node->right->parent = node;
        return;
    }

    //如果数相同直接不做操作
    if(funcPtr(node->data,element) == 0)
        return;

    if(funcPtr(node->data,element) > 0)
        //递归,和左孩子比较
<<<<<<< HEAD
        InsertNodeTree(node->left,element,funcPtr);
    else
        //递归,和右孩子比较
        InsertNodeTree(node->right,element,funcPtr);
=======
        InsertNode(node->left,element,funcPtr);
    else
        //递归,和右孩子比较
        InsertNode(node->right,element,funcPtr);
>>>>>>> 0979c5004e24bc00a548bec8efd3b8a77e34ab35
}

struct BinarySortTree
{
    //根节点
    BTNode *root;
};

ElementType GetNodeData(BTNode *n)
{
    if(n == NULL)
    {
        printf("节点不存在\n");
        return NULL;
    }
           
    else return n->data;
        
}

// 初始化二叉树
BSTree *InitBSTree()
{
    BSTree *tree = (BSTree*)malloc(sizeof(BSTree));
    if(tree == NULL)
    {
        printf("Init tree malloc error!\n");
        return NULL;
    }

    //二叉树的根可以为空
    tree->root = NULL;
    return tree;
}

void InsertElement(BSTree *tree, ElementType element,int(*funcPtr)(ElementType,ElementType))
{
    //如果根节点为空,直接放在根节点上
    if(tree->root == NULL)
        tree->root = CreateBTNode(element);

    else
<<<<<<< HEAD
        InsertNodeTree(tree->root,element,funcPtr);
=======
        InsertNode(tree->root,element,funcPtr);
>>>>>>> 0979c5004e24bc00a548bec8efd3b8a77e34ab35
}

//前序遍历
void TravelNodePrev(BTNode *node,void(*funcPtr)(ElementType))
{
    //终止条件
    if(node == NULL)
        return;

    //先打印根
    funcPtr(node->data);
    //再打印左孩子
    TravelNodePrev(node->left,funcPtr);
    //最后打印右孩子
    TravelNodePrev(node->right,funcPtr);
}
void TravelPrev(BSTree *tree,void(*funcPtr)(ElementType))
{
    TravelNodePrev(tree->root,funcPtr);
}

//中序遍历
void TravelNodeMid(BTNode *node,void(*funcPtr)(ElementType))
{
    //终止条件
    if(node == NULL)
        return;
    //先打印左孩子
        TravelNodeMid(node->left,funcPtr);
    //再打印根
    funcPtr(node->data);
    //最后打印右孩子
    TravelNodeMid(node->right,funcPtr);
}
void TravelMid(BSTree *tree,void(*funcPtr)(ElementType))
{
    TravelNodeMid(tree->root,funcPtr);
}

//后序遍历
void TravelNodePost(BTNode *node,void(*funcPtr)(ElementType))
{
    //终止条件
    if(node == NULL)
        return;

    //先打印左孩子
    TravelNodePost(node->left,funcPtr);
    //再打印右孩子
    TravelNodePost(node->right,funcPtr);
    //最后打印根
    funcPtr(node->data);
    
}
void TravelPost(BSTree *tree,void(*funcPtr)(ElementType))
{
    TravelNodePost(tree->root,funcPtr);
}

//查找树中节点
BTNode *FindNode(BTNode *node,ElementType element,int(*funcPtr)(ElementType,ElementType))
{
    if(node == NULL)
        return NULL;
    //当前节点的值等于要找的值
    if(funcPtr(node->data,element) == 0)
        return node;
    //当前节点的值大于要找的值,往左找
    else if(funcPtr(node->data,element) > 0)
    {
        return FindNode(node->left,element,funcPtr);
    }
    //当前节点的值小于要找的值,往右找
    else
    {
        return FindNode(node->right,element,funcPtr);
    }
}
<<<<<<< HEAD
BTNode *FindByElement(BSTree *tree, ElementType element,int(*funcPtr)(ElementType,ElementType))
=======
BTNode *                           FindByElement(BSTree *tree, ElementType element,int(*funcPtr)(ElementType,ElementType))
>>>>>>> 0979c5004e24bc00a548bec8efd3b8a77e34ab35
{
    return FindNode(tree->root,element,funcPtr);
}

//判断一个节点是不是另一个节点的左孩子
bool IsLeftChild(BTNode *parent,BTNode *child)
{
    if(parent->left == child)
        return true;
    return false;
}

//删除一个节点
void RemoveByElement(BSTree *tree, ElementType element,int(*funcPtr)(ElementType,ElementType))
{
    BTNode *node = FindByElement(tree,element,funcPtr);
    if(node == NULL)
        return;
    //要删除一个节点,需要先找到这个节点
    //该节点是叶子节点(左右孩子都空)
    if(node->left == NULL && node->right == NULL)
    {
        //如果该节点是根节点(整棵树就它一个节点)
        if(node->parent == NULL)
        {
            free(node);
            tree->root = NULL;
            return;
        }

        //该节点是双亲的左孩子
        if(IsLeftChild(node->parent,node) == true)
            node->parent->left = NULL;
        //该节点是双亲的右孩子
        else
            node->parent->right = NULL;
        
        free(node);
    }

    //左孩子不空,右孩子空
    else if(node->right == NULL)
    {
        node->left->parent = node->parent;
        //该节点是根节点
        if(node->parent == NULL)
        {
            tree->root = node->left;
            free(node);
            return;
        }

        //该节点是双亲的左孩子
        if(IsLeftChild(node->parent,node) == true)
            node->parent->left = node->left;
        //该节点是双亲的右孩子
        else
            node->parent->right = node->left;

        free(node);
    }
    //左孩子空,右孩子不空
    else if(node->left == NULL)
    {
        node->right->parent = node->parent;
        //该节点是根节点
        if(node->parent == NULL)
        {
            tree->root = node->right;
            free(node);
            return;
        }
        //该节点是双亲的左孩子
        if(IsLeftChild(node->parent,node) == true)
            node->parent->left = node->right;
        //该节点是双亲的右孩子
        else
            node->parent->right = node->right;

        free(node);
    }
    //左右孩子都不空
    else
    {
        //找右边子树最小的节点
        BTNode *MinNode = node->right;
        while(MinNode->left != NULL)
        {
            MinNode = MinNode->left;
        }

        //交换两个节点的值
        node->data = MinNode->data;

        //最左边的节点也可能有右子节点

        //如果右边子树的最小节点碰巧就是右孩子
        if(MinNode->parent == node)
            node->right = MinNode->right;
        else
            MinNode->parent->left = MinNode->right;
        free(MinNode);
    }
} 

int GetNumber(BTNode *node)
{
    if(node == NULL)
        return 0;
    
    //节点数量 = 左子树节点个数 + 右子树节点个数 + 1;
    return GetNumber(node->left) + GetNumber(node->right) + 1;
}

//获得树中节点数量
int GetNodeNumber(BSTree *tree)
{
    return GetNumber(tree->root);
}
<<<<<<< HEAD


BTNode *RotateLeft(BTNode *node)
{
    BTNode *t = node->right;
    
    t->parent = node->parent;
    node->right = t->left;
    t->left = node;
    node->parent = t;
    if(node->right != NULL)
        node->right->parent = node;
    

    return t;
}

BTNode *RotateRight(BTNode *node)
{
    if(node->left == NULL)
    {

    }
    BTNode *t = node->left;
    t->parent = node->parent;
    node->left = t->right;
    t->right = node;
    node->parent = t;
    t->right->parent = node;
    return t;
}

BTNode *RotateLeftRight(BTNode *node)
{
    node->left = RotateLeft(node->left);
    return RotateRight(node);
}

BTNode *RotateRightLeft(BTNode *node)
{
    node->right = RotateRight(node->right);
    return RotateLeft(node);
}

int GetNodeHeight(BTNode *node)
{
    if(node == NULL)
        return 0;
    
    int leftHeight = GetNodeHeight(node->left);
    int rightHeight = GetNodeHeight(node->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

int GetTreeHeight(BSTree *tree)
{
    if(tree->root == NULL)
        return 0;
    
    int leftHeight = GetNodeHeight(tree->root->left);
    int rightHeight = GetNodeHeight(tree->root->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}


BTNode *InsertNode(BTNode *node,ElementType element,int(*funcPtr)(ElementType,ElementType))
{
    if(node == NULL)
    {
        //node = CreateBTNode(element);
        return node;
    }
        
    if(funcPtr(node->data,element) > 0 && node->left == NULL)
    {
        node->left = CreateBTNode(element);
        if(node->left == NULL)
            return node;
        node->left->parent = node;
        
        return node;
    }
    if(funcPtr(node->data,element) < 0 && node->right == NULL)
    {
        node->right = CreateBTNode(element);
        if(node->right == NULL)
            return node;
        node->right->parent = node;
       
        return node;
    }
    // if(node->data == element)
    //     return node;
    if(funcPtr(node->data,element) > 0)
    {
        node->left = InsertNode(node->left,element,funcPtr);
        if(GetNodeHeight(node->left) - GetNodeHeight(node->right) > 1)
        {
            //左左插入
            if(funcPtr(node->left->data,element) > 0)
                node = RotateRight(node);
            //左右插入
            else
                node = RotateLeftRight(node);  
        }
    }
        
    if(funcPtr(node->data,element) < 0)
    {
        node->right = InsertNode(node->right,element,funcPtr);
        if(GetNodeHeight(node->right) - GetNodeHeight(node->left) > 1)
        {
            //右右插入
            if(funcPtr(node->right->data,element) < 0)
                node = RotateLeft(node);
            //右左插入
            else
                node = RotateRightLeft(node);
        }
    }
    return node;    
}
BTNode *GetTreeRoot(BSTree *tree)
{
    return tree->root;
}
void *InsertTree(BSTree *tree, ElementType element,int(*funcPtr)(ElementType,ElementType))
{
    if(tree->root == NULL)
        tree->root = CreateBTNode(element);
    else
        tree->root = InsertNode(tree->root,element,funcPtr);
}

BTNode *RemoveNodeElement(BTNode *node, ElementType element)
{
    // BTNode *node = FindNodeElement(root,element);
    // if(node == NULL)
    //     return root;
    BTNode *temp = node->parent;
    if(node->left == NULL && node->right == NULL)
    {
        if(node->parent == NULL)
        { 
            node = NULL;
            free(node);
            return temp;
        }
        if(IsLeftChild(node->parent,node) == true)
            node->parent->left = NULL;
        else
            node->parent->right = NULL;
        free(node);
        return NULL;
    }
    else if(node->left == NULL)
    {
        node->right->parent = node->parent;
        if(node->parent == NULL)
        {
            node = node->right;
            free(node->right);
            return node;
        }
        if(IsLeftChild(node->parent,node) == true)
            node->parent->left = node->right;
        else
            node->parent->right = node->right;
        free(node);
        return temp->right;
    }
    else if(node->right == NULL)
    {
        node->left->parent = node->parent;
        if(node == NULL)
        {
            node = node->left;
            free(node->left);
            return node;
        }
        if(IsLeftChild(node->parent,node) == true)
            node->parent->left = node->left;
        else
            node->parent->right = node->left;
        free(node);
        return temp->left;
    }
    else
    {
        BTNode *MinNode = node->right;
        while(MinNode->left != NULL)
        {
            MinNode = MinNode->left;
        }
        node->data = MinNode->data;
        if(node->right == MinNode)
            node->right = MinNode->right;
        else
            MinNode->parent->left = MinNode->left;
        free(MinNode);
        return node;
    }
}



BTNode *DeleteNode(BTNode *node,ElementType element,int(*funcPtr)(ElementType,ElementType))
{
    if(node == NULL)
        return NULL;

    if(funcPtr(node->data,element) > 0)
    {
        node->left = DeleteNode(node->left,element,funcPtr);
        //右子树重
        if(GetNodeHeight(node->right) - GetNodeHeight(node->left) > 1)
        {
            //右孩子的左子树比右子树高
            //右左
            if(GetNodeHeight(node->right->left) - GetNodeHeight(node->right->right) > 0)
                node = RotateRightLeft(node);
            else
                node = RotateLeft(node);
        }
    }
    else if(funcPtr(node->data,element) < 0)
    {
        node->right = DeleteNode(node->right,element,funcPtr);
        //左边重
        if(GetNodeHeight(node->left) - GetNodeHeight(node->right) > 1)
        {
            //左左
            if(GetNodeHeight(node->left->left) - GetNodeHeight(node->left->right) > 0)
                node = RotateRight(node);
            //左右
            else
                node = RotateLeftRight(node);
        }
    }
    //找到要删除的节点
    else
    {
        node = RemoveNodeElement(node,element);
    }
    return node;
}
void *DeleteTree(BSTree *tree, ElementType element,int(*funcPtr)(ElementType,ElementType))
{
    tree->root = DeleteNode(tree->root,element,funcPtr);
}
=======
>>>>>>> 0979c5004e24bc00a548bec8efd3b8a77e34ab35
